package com.learning.algorithm.sort.divideAndConquer;

import com.learning.algorithm.sort.ArraysUtil;
import com.learning.algorithm.sort.CheckSort;
import com.learning.algorithm.sort.IntArraySort;
import com.learning.algorithm.sort.simpleSort.SelectSort;

import java.util.Arrays;

/**
 * @Author: lishi
 * @Description: ${description}
 * @Date: 2021/11/22 15:04
 */
public class MergeSort implements IntArraySort {
    public static int[] mergeSort(int[] arrays) {
        return childSort(arrays);
    }

    public static int[] childSort(int[] arrays) {
        if (arrays.length == 1) {
            return arrays;
        }
        if (arrays.length == 2) {
            SelectSort.selectSort(arrays);
            return arrays;
        }

        int individePos = arrays.length / 2;
        int[] rightArray = new int[individePos];
        System.arraycopy(arrays, 0, rightArray, 0, individePos);
        int[] leftArray = new int[arrays.length - individePos];
        System.arraycopy(arrays, individePos, leftArray, 0, arrays.length - individePos);

        rightArray = childSort(rightArray);
        leftArray = childSort(leftArray);
        int[] resultArray = new int[arrays.length];
        int rightIndex = 0;
        int leftIndex = 0;
        for (int i = 0; i < resultArray.length; i++) {
            if (leftIndex > leftArray.length - 1) {
                resultArray[i] = rightArray[rightIndex];
                rightIndex++;
                continue;
            }
            if (rightIndex > rightArray.length - 1) {
                resultArray[i] = leftArray[leftIndex];
                leftIndex++;
                continue;
            }

            if (rightArray[rightIndex] >= leftArray[leftIndex]) {
                resultArray[i] = leftArray[leftIndex];
                leftIndex++;
                continue;
            }

            if (rightArray[rightIndex] < leftArray[leftIndex]) {
                resultArray[i] = rightArray[rightIndex];
                rightIndex++;
                continue;
            }

        }
        return resultArray;
    }

    public static void main(String[] args) {
        int length = 10000000;
        int[] originArrays = ArraysUtil.genNoDuplicateIntArray(length);
        int[] cloneArrays = new int[length];
        System.arraycopy(originArrays, 0, cloneArrays, 0, length);
        //        System.out.println(Arrays.toString(originArrays));
        cloneArrays = mergeSort(cloneArrays);
        //        System.out.println(Arrays.toString(cloneArrays));
        System.out.println(CheckSort.checkSortResult(originArrays, cloneArrays));

    }

    public int[] sort(int[] arrays) {
        return mergeSort(arrays);
    }

    public String getDesc() {
        return "并归排序";
    }
}
